home *** CD-ROM | disk | FTP | other *** search
/ Chip 2007 January, February, March & April / Chip-Cover-CD-2007-02.iso / Pakiet bezpieczenstwa / mini Pentoo LiveCD 2006.1 / mpentoo-2006.1.iso / livecd.squashfs / usr / lib / python2.4 / site-packages / Crypto / Protocol / AllOrNothing.py < prev    next >
Text File  |  2006-06-22  |  11KB  |  296 lines
  1. """This file implements all-or-nothing package transformations.
  2.  
  3. An all-or-nothing package transformation is one in which some text is
  4. transformed into message blocks, such that all blocks must be obtained before
  5. the reverse transformation can be applied.  Thus, if any blocks are corrupted
  6. or lost, the original message cannot be reproduced.
  7.  
  8. An all-or-nothing package transformation is not encryption, although a block
  9. cipher algorithm is used.  The encryption key is randomly generated and is
  10. extractable from the message blocks.
  11.  
  12. This class implements the All-Or-Nothing package transformation algorithm
  13. described in:
  14.  
  15. Ronald L. Rivest.  "All-Or-Nothing Encryption and The Package Transform"
  16. http://theory.lcs.mit.edu/~rivest/fusion.pdf
  17.  
  18. """
  19.  
  20. __revision__ = "$Id: AllOrNothing.py,v 1.8 2003/02/28 15:23:20 akuchling Exp $"
  21.  
  22. import operator
  23. import string
  24. from Crypto.Util.number import bytes_to_long, long_to_bytes
  25.  
  26.  
  27.  
  28. class AllOrNothing:
  29.     """Class implementing the All-or-Nothing package transform.
  30.  
  31.     Methods for subclassing:
  32.  
  33.         _inventkey(key_size):
  34.             Returns a randomly generated key.  Subclasses can use this to
  35.             implement better random key generating algorithms.  The default
  36.             algorithm is probably not very cryptographically secure.
  37.  
  38.     """
  39.  
  40.     def __init__(self, ciphermodule, mode=None, IV=None):
  41.         """AllOrNothing(ciphermodule, mode=None, IV=None)
  42.  
  43.         ciphermodule is a module implementing the cipher algorithm to
  44.         use.  It must provide the PEP272 interface.
  45.  
  46.         Note that the encryption key is randomly generated
  47.         automatically when needed.  Optional arguments mode and IV are
  48.         passed directly through to the ciphermodule.new() method; they
  49.         are the feedback mode and initialization vector to use.  All
  50.         three arguments must be the same for the object used to create
  51.         the digest, and to undigest'ify the message blocks.
  52.         """
  53.  
  54.         self.__ciphermodule = ciphermodule
  55.         self.__mode = mode
  56.         self.__IV = IV
  57.         self.__key_size = ciphermodule.key_size
  58.         if self.__key_size == 0:
  59.             self.__key_size = 16
  60.  
  61.     __K0digit = chr(0x69)
  62.  
  63.     def digest(self, text):
  64.         """digest(text:string) : [string]
  65.  
  66.         Perform the All-or-Nothing package transform on the given
  67.         string.  Output is a list of message blocks describing the
  68.         transformed text, where each block is a string of bit length equal
  69.         to the ciphermodule's block_size.
  70.         """
  71.  
  72.         # generate a random session key and K0, the key used to encrypt the
  73.         # hash blocks.  Rivest calls this a fixed, publically-known encryption
  74.         # key, but says nothing about the security implications of this key or
  75.         # how to choose it.
  76.         key = self._inventkey(self.__key_size)
  77.         K0 = self.__K0digit * self.__key_size
  78.  
  79.         # we need two cipher objects here, one that is used to encrypt the
  80.         # message blocks and one that is used to encrypt the hashes.  The
  81.         # former uses the randomly generated key, while the latter uses the
  82.         # well-known key.
  83.         mcipher = self.__newcipher(key)
  84.         hcipher = self.__newcipher(K0)
  85.  
  86.         # Pad the text so that its length is a multiple of the cipher's
  87.         # block_size.  Pad with trailing spaces, which will be eliminated in
  88.         # the undigest() step.
  89.         block_size = self.__ciphermodule.block_size
  90.         padbytes = block_size - (len(text) % block_size)
  91.         text = text + ' ' * padbytes
  92.  
  93.         # Run through the algorithm:
  94.         # s: number of message blocks (size of text / block_size)
  95.         # input sequence: m1, m2, ... ms
  96.         # random key K' (`key' in the code)
  97.         # Compute output sequence: m'1, m'2, ... m's' for s' = s + 1
  98.         # Let m'i = mi ^ E(K', i) for i = 1, 2, 3, ..., s
  99.         # Let m's' = K' ^ h1 ^ h2 ^ ... hs
  100.         # where hi = E(K0, m'i ^ i) for i = 1, 2, ... s
  101.         #
  102.         # The one complication I add is that the last message block is hard
  103.         # coded to the number of padbytes added, so that these can be stripped
  104.         # during the undigest() step
  105.         s = len(text) / block_size
  106.         blocks = []
  107.         hashes = []
  108.         for i in range(1, s+1):
  109.             start = (i-1) * block_size
  110.             end = start + block_size
  111.             mi = text[start:end]
  112.             assert len(mi) == block_size
  113.             cipherblock = mcipher.encrypt(long_to_bytes(i, block_size))
  114.             mticki = bytes_to_long(mi) ^ bytes_to_long(cipherblock)
  115.             blocks.append(mticki)
  116.             # calculate the hash block for this block
  117.             hi = hcipher.encrypt(long_to_bytes(mticki ^ i, block_size))
  118.             hashes.append(bytes_to_long(hi))
  119.  
  120.         # Add the padbytes length as a message block
  121.         i = i + 1
  122.         cipherblock = mcipher.encrypt(long_to_bytes(i, block_size))
  123.         mticki = padbytes ^ bytes_to_long(cipherblock)
  124.         blocks.append(mticki)
  125.  
  126.         # calculate this block's hash
  127.         hi = hcipher.encrypt(long_to_bytes(mticki ^ i, block_size))
  128.         hashes.append(bytes_to_long(hi))
  129.  
  130.         # Now calculate the last message block of the sequence 1..s'.  This
  131.         # will contain the random session key XOR'd with all the hash blocks,
  132.         # so that for undigest(), once all the hash blocks are calculated, the
  133.         # session key can be trivially extracted.  Calculating all the hash
  134.         # blocks requires that all the message blocks be received, thus the
  135.         # All-or-Nothing algorithm succeeds.
  136.         mtick_stick = bytes_to_long(key) ^ reduce(operator.xor, hashes)
  137.         blocks.append(mtick_stick)
  138.  
  139.         # we convert the blocks to strings since in Python, byte sequences are
  140.         # always represented as strings.  This is more consistent with the
  141.         # model that encryption and hash algorithms always operate on strings.
  142.         return map(long_to_bytes, blocks)
  143.  
  144.  
  145.     def undigest(self, blocks):
  146.         """undigest(blocks : [string]) : string
  147.  
  148.         Perform the reverse package transformation on a list of message
  149.         blocks.  Note that the ciphermodule used for both transformations
  150.         must be the same.  blocks is a list of strings of bit length
  151.         equal to the ciphermodule's block_size.
  152.         """
  153.  
  154.         # better have at least 2 blocks, for the padbytes package and the hash
  155.         # block accumulator
  156.         if len(blocks) < 2:
  157.             raise ValueError, "List must be at least length 2."
  158.  
  159.         # blocks is a list of strings.  We need to deal with them as long
  160.         # integers
  161.         blocks = map(bytes_to_long, blocks)
  162.  
  163.         # Calculate the well-known key, to which the hash blocks are
  164.         # encrypted, and create the hash cipher.
  165.         K0 = self.__K0digit * self.__key_size
  166.         hcipher = self.__newcipher(K0)
  167.  
  168.         # Since we have all the blocks (or this method would have been called
  169.         # prematurely), we can calcualte all the hash blocks.
  170.         hashes = []
  171.         for i in range(1, len(blocks)):
  172.             mticki = blocks[i-1] ^ i
  173.             hi = hcipher.encrypt(long_to_bytes(mticki))
  174.             hashes.append(bytes_to_long(hi))
  175.  
  176.         # now we can calculate K' (key).  remember the last block contains
  177.         # m's' which we don't include here
  178.         key = blocks[-1] ^ reduce(operator.xor, hashes)
  179.  
  180.         # and now we can create the cipher object
  181.         mcipher = self.__newcipher(long_to_bytes(key))
  182.         block_size = self.__ciphermodule.block_size
  183.  
  184.         # And we can now decode the original message blocks
  185.         parts = []
  186.         for i in range(1, len(blocks)):
  187.             cipherblock = mcipher.encrypt(long_to_bytes(i, block_size))
  188.             mi = blocks[i-1] ^ bytes_to_long(cipherblock)
  189.             parts.append(mi)
  190.  
  191.         # The last message block contains the number of pad bytes appended to
  192.         # the original text string, such that its length was an even multiple
  193.         # of the cipher's block_size.  This number should be small enough that
  194.         # the conversion from long integer to integer should never overflow
  195.         padbytes = int(parts[-1])
  196.         text = string.join(map(long_to_bytes, parts[:-1]), '')
  197.         return text[:-padbytes]
  198.  
  199.     def _inventkey(self, key_size):
  200.         # TBD: Not a very secure algorithm.  Eventually, I'd like to use JHy's
  201.         # kernelrand module
  202.         import time
  203.         from Crypto.Util import randpool
  204.         # TBD: key_size * 2 to work around possible bug in RandomPool?
  205.         pool = randpool.RandomPool(key_size * 2)
  206.         while key_size > pool.entropy:
  207.             pool.add_event()
  208.  
  209.         # we now have enough entropy in the pool to get a key_size'd key
  210.         return pool.get_bytes(key_size)
  211.  
  212.     def __newcipher(self, key):
  213.         if self.__mode is None and self.__IV is None:
  214.             return self.__ciphermodule.new(key)
  215.         elif self.__IV is None:
  216.             return self.__ciphermodule.new(key, self.__mode)
  217.         else:
  218.             return self.__ciphermodule.new(key, self.__mode, self.__IV)
  219.  
  220.  
  221.  
  222. if __name__ == '__main__':
  223.     import sys
  224.     import getopt
  225.     import base64
  226.  
  227.     usagemsg = '''\
  228. Test module usage: %(program)s [-c cipher] [-l] [-h]
  229.  
  230. Where:
  231.     --cipher module
  232.     -c module
  233.         Cipher module to use.  Default: %(ciphermodule)s
  234.  
  235.     --aslong
  236.     -l
  237.         Print the encoded message blocks as long integers instead of base64
  238.         encoded strings
  239.  
  240.     --help
  241.     -h
  242.         Print this help message
  243. '''
  244.  
  245.     ciphermodule = 'AES'
  246.     aslong = 0
  247.  
  248.     def usage(code, msg=None):
  249.         if msg:
  250.             print msg
  251.         print usagemsg % {'program': sys.argv[0],
  252.                           'ciphermodule': ciphermodule}
  253.         sys.exit(code)
  254.  
  255.     try:
  256.         opts, args = getopt.getopt(sys.argv[1:],
  257.                                    'c:l', ['cipher=', 'aslong'])
  258.     except getopt.error, msg:
  259.         usage(1, msg)
  260.  
  261.     if args:
  262.         usage(1, 'Too many arguments')
  263.  
  264.     for opt, arg in opts:
  265.         if opt in ('-h', '--help'):
  266.             usage(0)
  267.         elif opt in ('-c', '--cipher'):
  268.             ciphermodule = arg
  269.         elif opt in ('-l', '--aslong'):
  270.             aslong = 1
  271.  
  272.     # ugly hack to force __import__ to give us the end-path module
  273.     module = __import__('Crypto.Cipher.'+ciphermodule, None, None, ['new'])
  274.  
  275.     a = AllOrNothing(module)
  276.     print 'Original text:\n=========='
  277.     print __doc__
  278.     print '=========='
  279.     msgblocks = a.digest(__doc__)
  280.     print 'message blocks:'
  281.     for i, blk in map(None, range(len(msgblocks)), msgblocks):
  282.         # base64 adds a trailing newline
  283.         print '    %3d' % i,
  284.         if aslong:
  285.             print bytes_to_long(blk)
  286.         else:
  287.             print base64.encodestring(blk)[:-1]
  288.     #
  289.     # get a new undigest-only object so there's no leakage
  290.     b = AllOrNothing(module)
  291.     text = b.undigest(msgblocks)
  292.     if text == __doc__:
  293.         print 'They match!'
  294.     else:
  295.         print 'They differ!'
  296.